class Solution:
    def magic_fast(self, arr):
        def recur_magic_fast(start, end):
            # 终结条件
            if start > end:
                return -1
            mid = (start + end) // 2
            if arr[mid] == mid:
                return mid
            # 找左边
            left_end = min(mid - 1, arr[mid])
            left_ans = recur_magic_fast(start, left_end)
            if left_ans != -1:
                return left_ans
            # 找右边
            right_start = max(mid + 1, arr[mid])
            right_ans = recur_magic_fast(right_start, end)
            return right_ans

        return recur_magic_fast(0, len(arr) - 1)


arr = [-5, -2, 0, 1, 4, 6, 7]
arr2 = [0]
arr3 = [1, 1, 1, 1, 1]

solution = Solution()
ans = solution.magic_fast(arr3)
print(ans)
